# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/11/4
# @File : 32.(数位DP02）从1到n整数中1出现的次数.py
# https://www.acwing.com/problem/content/description/51/
# https://www.acwing.com/video/180/
"""
输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。

例如输入 12，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，11 和 12，其中 “1” 一共出现了 5 次。

"""

class Solution(object):
    def numberOf1Between1AndN_Solution(self, n):
        """
        :type n: int
        :rtype: int
        """
        if(not n):
            return 0
        bit = []
        while(n):
            bit.append(n%10)
            n = n // 10
        res = 0
        for i in range(len(bit)-1,-1,-1):
            l = 0
            r = 0
            t = 1
            for j in range(len(bit)-1,i,-1):#数左边的0到ab-1
                l = l * 10 + bit[j]
            for j in range(i-1,-1,-1):#数右边的0到def、和右边全要（t）
                r = r * 10 + bit[j]
                t *= 10
            res += l * t#0-(ab-1)
            #左边取ab：分为遍历到的这一位是1还是大于1，等于0就是不用计算了，因为这一位没有1了。
            if(bit[i]==1):
                res += (r + 1)
            elif(bit[i]>1):
                res += t
        return res